package com.eddie.tenalgorithm.dac;

/**
 * @author Eddie
 * @date 2022/08/15 16:57
 **/
public class Hanoitower {

    public static void main(String[] args) {
        hanoiTower(2, "起点", "中转", "终点");
    }

    /**
     * 汉诺塔移动方案
     * 使用分治算法
     */
    public static void hanoiTower(int num, String a, String b, String c) {
        //如果只有一个盘
        if (num == 1) {
            System.out.println("第1个盘从" + a + "->" + c);
        } else {
            //如果n >=2 情况，就可以视为两个盘1、最下面的一个盘，2、上面的所有盘
            //1、先把最上面的盘 A -> B，移动过程会使用到c
            hanoiTower(num - 1, a, c, b);
            //2、把最下面的A-C
            System.out.println("第" + num + "个盘从" + a + "->" + c);
            //3、把b塔所有盘从B -> C,移动过程使用到a塔
            hanoiTower(num - 1, b, a, c);
        }
    }
}
